#include <bits/stdc++.h>

using namespace std;

// 全O(1)的数据结构
// 测试链接 : https://leetcode.cn/problems/all-oone-data-structure/

class AllOne
{
private:
    class Bucket
    {
    public:
        unordered_set<string> set;
        int cnt;
        Bucket* prev;
        Bucket* next;

        Bucket(const string& str, int c)
        {
            set.emplace(str);
            cnt = c;
            prev = nullptr;
            next = nullptr;
        }
    };

    void afterInsert(Bucket* prevBucket, Bucket* newBucket)
    {
        // prevBucket newBucket nextBucket
        Bucket* nextBucket = prevBucket->next;
        prevBucket->next = newBucket;
        newBucket->prev = prevBucket;
        nextBucket->prev = newBucket;
        newBucket->next = nextBucket;
    }

    void remove(Bucket* curBucket)
    {
        // prevBucket curBucket nextBucket
        curBucket->prev->next = curBucket->next;
        curBucket->next->prev = curBucket->prev;
        delete curBucket; // 释放内存
    }

    Bucket* head = nullptr;
    Bucket* tail = nullptr;
    unordered_map<string, Bucket*> m;

public:
    AllOne()
    {
        head = new Bucket("", 0);
        tail = new Bucket("", INT_MAX);
        head->next = tail;
        tail->prev = head;
    }

    void inc(string key)
    {
        if(!m.count(key))
        {
            if(head->next->cnt == 1) // 有出现频率为 1 的桶
            {
                head->next->set.emplace(key);
                m[key] = head->next;
            }
            else
            {
                Bucket* newBucket = new Bucket(key, 1); // 没有出现频率为 1 的桶
                afterInsert(head, newBucket);
                m[key] = newBucket;
            }
        }
        else
        {
            Bucket* bucket = m[key];
            int cnt = bucket->cnt;
            if(bucket->next->cnt == cnt + 1) // 有出现频率为 cnt + 1 的桶
            {
                bucket->next->set.insert(key);
                m[key] = bucket->next;
            }
            else // 没有出现频率为 cnt + 1 的桶
            {
                Bucket* newBucket = new Bucket(key, cnt + 1);
                m[key] = newBucket;
                afterInsert(bucket, newBucket);
            }
            bucket->set.erase(key);
            if(bucket->set.empty()) remove(bucket);
        }
    }

    void dec(string key)
    {
        Bucket* bucket = m[key];
        int cnt = bucket->cnt;
        if(cnt == 1) // 出现次数为 1，则需要从哈希中删掉
        {
            m.erase(key);
        }
        else
        {
            if(bucket->prev->cnt == cnt - 1) // 有出现频率为 cnt - 1 的桶
            {
                bucket->prev->set.emplace(key);
                m[key] = bucket->prev;
            }
            else // 没有出现频率为 cnt - 1 的桶
            {
                Bucket* newBucket = new Bucket(key, cnt - 1);
                m[key] = newBucket;
                afterInsert(bucket->prev, newBucket);
            }
        }
        bucket->set.erase(key);
        if(bucket->set.empty()) remove(bucket);
    }

    string getMaxKey()
    {
        return *(tail->prev->set.begin());
    }

    string getMinKey()
    {
        return *(head->next->set.begin());
    }
};